package org.basis.algorithm.window;

import java.util.HashSet;

/**
 * 滑动窗口经典解法
 *
 * @author Mr_wenpan@163.com 2022/2/12 12:55 下午
 */
public class SlidingWindow {

    public static void main(String[] args) {
        int str = lengthOfLongestSubstring3("abcabcbb");
        System.out.println(str);
    }

    /**
     * 滑动窗口解法
     */
    public static int lengthOfLongestSubstring3(String s) {
        if (s == null || s.length() < 1) {
            return 0;
        }
        if (s.length() == 1) {
            return 1;
        }
        int res = Integer.MIN_VALUE;
        int r = 0;
        char[] chars = s.toCharArray();
        HashSet<Character> set = new HashSet<>();
        // 遍历左边界
        for (int i = 0; i < chars.length; i++) {
            while (i <= r && r < chars.length && !set.contains(chars[r])) {
                set.add(chars[r]);
                r++;
            }
            // 一旦发现set里有重复字符，那么就开始结算
            res = Math.max(res, r - i);
            // 将最左边界的元素去除
            set.remove(chars[i]);
        }

        return res;
    }

    /**
     * 双指针解法
     */
    public static int lengthOfLongestSubstring2(String s) {
        if (s == null || s.length() < 1) {
            return 0;
        }
        if (s.length() == 1) {
            return 1;
        }
        int l = 0;
        int r = 0;
        int res = 0;
        HashSet<Character> set = new HashSet<>();
        char[] chars = s.toCharArray();

        while (l <= r && r < chars.length) {
            if (set.contains(chars[r])) {
                // 结算最大子串长度
                res = Math.max(res, r - l);
                // 左指针右移一个，并且移除已经失效的
                set.remove(chars[l++]);
            } else {
                set.add(chars[r]);
                // 右指针往右移动一个单位
                r++;
            }
        }

        // 最后一次结算
        res = Math.max(res, r - l);

        return res;
    }

    /**
     * 经典窗口解法
     */
    public static int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() < 1) {
            return 0;
        }
        if (s.length() == 1) {
            return 1;
        }

        int res = 0;
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            HashSet<Character> set = new HashSet<>();
            int j;
            for (j = i; j < chars.length; j++) {
                if (!set.contains(chars[j])) {
                    set.add(chars[j]);
                } else {
                    break;
                }
            }
            // 结算
            res = Math.max(res, j - i);
        }

        return res;
    }
}